﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;

/// <summary>
/// Summary description for Algorithm
/// </summary>
public class Algorithm
{
	public Algorithm()
	{
		//
		// TODO: Add constructor logic here
		//
	}
    
    public static double lenghtPointToPoint(double longitude1, double latitude1, double longitude2, double latitude2)
    {
        return Math.Sqrt((longitude1 - longitude2) * (longitude1 - longitude2) + (latitude1 - latitude2) * (latitude1 - latitude2));
    }
    public static double lenghtStationToStationbyID(int idStation1, int idStation2)
    {
        Station s1 = Data.stations.Single(p=>p.IDStation==idStation1);
        Station s2 = Data.stations.Single(p=>p.IDStation==idStation2);
        return lenghtPointToPoint(s1.Longitude.Value, s1.Latitude.Value, s2.Longitude.Value, s2.Latitude.Value);
    }
    public static double lenghtStationToStationbyIndex(int stationIndex1, int stationIndex2)
    {
        Station s1 = Data.stations[stationIndex1];
        Station s2 = Data.stations[stationIndex2];
        return lenghtPointToPoint(s1.Longitude.Value, s1.Latitude.Value, s2.Longitude.Value, s2.Latitude.Value);
    }
    public static int[] AStart(Vertex[] v, int startIndex, int endIndex)
    {
        bool hasResult = true;
        List<int> open = new List<int>();
        List<int> close = new List<int>();
        open.Add(startIndex);
        v[startIndex].g = 0;
        while (true)
        {
            //if OPEN is empty before go to end point => no result
            if (open.Count == 0)
            {
                hasResult = false;
                break;
            }
            //=================================================================
            //Chooooooooooose Tmax, f'(Tmax) must be minimize in open
            int tmaxindexinopen = 0;
            for (int i = 1; i < open.Count; i++)
            {
                if (v[open[i]].g + v[open[i]].hh < v[open[tmaxindexinopen]].g + v[open[tmaxindexinopen]].hh)
                    tmaxindexinopen = i;
            }
            //Create Tmax
            int Tmax = open[tmaxindexinopen];
            //Pop Tmax out OPEN
            open.RemoveAt(tmaxindexinopen);
            //Push Tmax in CLOSE
            close.Add(Tmax);
            Console.Write("\nTmax = " + v[Tmax].id + "\n");
            //=================================================================
            //If Tmax == endIndex, result found!!!!!!!!!!
            if (Tmax == endIndex)
            {
                hasResult = true;
                break;
            }
            //=================================================================
            //Examine all next vertex of Tmax
            for (int Tk_index = 0; Tk_index < v[Tmax].next.Count; Tk_index++)
            {
                int Tk = v[Tmax].next[Tk_index];
                double Tk_value = v[Tmax].nextValue[Tk_index];
                //if Tk in OPEN
                if (open.IndexOf(Tk) > -1)
                {
                    if (v[Tmax].g + Tk_value < v[Tk].g)
                    {
                        v[Tk].before = Tmax;
                        v[Tk].g = v[Tmax].g + Tk_value;
                    }
                }
                //if Tk in CLOSE
                if (close.IndexOf(Tk) > -1)
                {
                    if (v[Tmax].g + Tk_value < v[Tk].g)
                    {
                        v[Tk].before = Tmax;
                        v[Tk].g = v[Tmax].g + Tk_value;
                    }
                }
                //if Tk is not in CLOSE, OPEN
                if (close.IndexOf(Tk) < 0 && open.IndexOf(Tk) < 0)
                {
                    v[Tk].g = v[Tmax].g + Tk_value;
                    v[Tk].before = Tmax;
                    open.Add(Tk);
                }
            }
            foreach (Vertex t in v)
            {
                Console.Write("ID = "
                              + t.id
                              + "\tg = "
                              + t.g
                              + "\th' = "
                              + t.hh
                              + "\tbefore = "
                              + t.before
                              + "\n"
                              );
            }
            Console.Write("\nOpen: ");
            foreach (int i in open)
                Console.Write(v[i].id.ToString() + " ");
            Console.Write("\nClose: ");
            foreach (int i in close)
                Console.Write(v[i].id.ToString() + " ");
            Console.Write("\n=========================================\n\n");
        }
        if (hasResult)
        {
            List<int> result = new List<int>();
            while (true)
            {
                result.Add(endIndex);
                endIndex = v[endIndex].before;
                if (endIndex == -1)
                    break;
            }
            return result.ToArray();
        }
        return new int[0];
    }

    public static int[] AStart(Vertex[] v, int startIndex, int endIndex, double walk, double changeRoute)
    {
        walk = toUnrealDistance(walk);
        changeRoute = toUnrealDistance(changeRoute);
        bool hasResult = true;
        List<int> open = new List<int>();
        List<int> close = new List<int>();
        open.Add(startIndex);
        v[startIndex].g = 0;
        for (int i=0; i < v.Length; i++)
        {
            //Station crr = Data.stations.Single(p=>p.IDStation==v[i].id);
            //Station end = Data.stations.Single(p=>p.IDStation==endIndex);
            //v[i].hh = lenghtPointToPoint(crr.Longitude.Value, crr.Latitude.Value, end.Longitude.Value, end.Latitude.Value);
        }
        while (true)
        {
            //if OPEN is empty before go to end point => no result
            if (open.Count == 0)
            {
                hasResult = false;
                break;
            }
            //=================================================================
            //Chooooooooooose Tmax, f'(Tmax) must be minimize in open
            int tmaxindexinopen = 0;
            for (int i = 1; i < open.Count; i++)
            {
                if (v[open[i]].g + v[open[i]].hh < v[open[tmaxindexinopen]].g + v[open[tmaxindexinopen]].hh)
                    tmaxindexinopen = i;
            }
            //Create Tmax
            int Tmax = open[tmaxindexinopen];
            //Pop Tmax out OPEN
            open.RemoveAt(tmaxindexinopen);
            //Push Tmax in CLOSE
            close.Add(Tmax);
            //=================================================================
            //If Tmax == endIndex, result found!!!!!!!!!!
            if (Tmax == endIndex)
            {
                hasResult = true;
                break;
            }
            //=================================================================
            //Examine all next vertex of Tmax
            for (int Tk_index = 0; Tk_index < v[Tmax].next.Count; Tk_index++)
            {
                int Tk = v[Tmax].next[Tk_index];
                double Tk_value = v[Tmax].nextValue[Tk_index];
                //if Tk in OPEN
                if (open.IndexOf(Tk) > -1)
                {
                    if (v[Tmax].g + Tk_value < v[Tk].g)
                    {
                        v[Tk].before = Tmax;
                        v[Tk].g = v[Tmax].g + Tk_value;
                    }
                }
                //if Tk in CLOSE
                if (close.IndexOf(Tk) > -1)
                {
                    if (v[Tmax].g + Tk_value < v[Tk].g)
                    {
                        v[Tk].before = Tmax;
                        v[Tk].g = v[Tmax].g + Tk_value;
                    }
                }
                //if Tk is not in CLOSE, OPEN
                if (close.IndexOf(Tk) < 0 && open.IndexOf(Tk) < 0)
                {
                    v[Tk].g = v[Tmax].g + Tk_value;
                    v[Tk].before = Tmax;
                    open.Add(Tk);
                }
            }
        }
        if (hasResult)
        {
            List<int> result = new List<int>();
            while (true)
            {
                result.Add(endIndex);
                endIndex = v[endIndex].before;
                if (endIndex == -1)
                    break;
            }
            return result.ToArray();
        }
        return new int[0];
    }
    public static string[] changeStationToLine(int[] arr, List<Vertex> station)
    {
        /*try
        {
            
            string result = "";
            for (int i = 0; i < arr.Length / 2; i++)
            {
                int temp = arr[i];
                arr[i] = arr[arr.Length - 1 - i];
                arr[arr.Length - 1 - i] = temp;
            }
            bool firstOne = true;
            for (int i = 1; i < arr.Length - 2; i++)
            {
                int beginStationID = station[arr[i]].id;
                int endStationID = station[arr[i+1]].id;
                if (beginStationID == endStationID)
                    continue;
                StationToStation s2s = Data.stationToStation.Single(p => p.IDStartStation == beginStationID && p.IDEndStation == endStationID);
                if (firstOne == true)
                    firstOne = false;
                else
                    result += ";";
                    result += s2s.Nodes;
            }
            return result;
        }
        catch
        {
            return "";
        }*/
        for (int i = 0; i < arr.Length / 2; i++)
        {
            int temp = arr[i];
            arr[i] = arr[arr.Length - 1 - i];
            arr[arr.Length - 1 - i] = temp;
        }
        List<string> result = new List<string>();
        int from = 0, to = 0;
        for (int i = 0; i < arr.Length; i++)
        {
            if ((station[arr[i]].flag != station[arr[from]].flag)||(i == arr.Length-1))
            {
                string a;
                if (i == arr.Length-1)
                    a = changeStationToLine(arr, station, from, i);
                else
                    a = changeStationToLine(arr, station, from, i - 1);
                if (a != "")
                    result.Add(a);
                from = i;
            }
        }
        //Trường hợp đặt biệt
        if (arr.Length == 2)
        {
            result = new List<string>();
            string a = changeStationToLine(arr, station, 0, 1);
            result.Add(a);
        }
        //Hết
        result.Add(getDirection(arr, station));
        return result.ToArray();
    }
    public static string changeStationToLine(int[] arr, List<Vertex> station, int from, int to)
    {
        try
        {
            string result = "";
            bool firstOne = true;
            for (int i = from; i < to; i++)
            {
                int beginStationID = station[arr[i]].id;
                int endStationID = station[arr[i+1]].id;
                if (beginStationID == endStationID)
                    continue;
                StationToStation s2s = Data.stationToStation.Where(p => p.IDStartStation == beginStationID && p.IDEndStation == endStationID).ToArray()[0];
                if (firstOne == true)
                    firstOne = false;
                else
                    result += ";";
                result += s2s.Nodes;
            }
            return result;
        }
        catch
        {
            return "";
        }
    }
    public static string getDirection(int[] arr, List<Vertex> station)
    {
        Station st = Data.stations.Single(p => p.IDStation == station[arr[0]].id);
        string result = "-->Bắt đầu từ trạm " + st.AddressNumber + "," + st.StreetName + "<br/>";
        for (int i = 1; i < arr.Length; i++)
        {
            Vertex before = station[arr[i-1]];
            Vertex current = station[arr[i]];
            st = Data.stations.Single(p => p.IDStation == current.id);

            if (current.flag > -1 && before.flag == -1)
            {
                BusRoute br = Data.busRoutes.Single(p => p.IDBusRoute == current.flag);
                result += "-->Đón xe số " + br.BusRouteNumber + "<br/>";
            }
            if (current.flag == -1 && before.flag > -1)
                result += "-->Xuống xe ở trạm " + st.AddressNumber + "," + st.StreetName + "<br/>";
            if (current.flag == -1 && before.flag == -1)
            {
                while ((i < arr.Length-1) && (station[arr[i+1]].flag == -1)) i++;
                if (i == arr.Length - 1)
                    result += "-->Đi bộ về đích.";
                else if (i < arr.Length - 1)
                {
                    st = Data.stations.Single(p => p.IDStation == station[arr[i]].id);
                    result += "-->Đi bộ đến trạm " + st.AddressNumber + "," + st.StreetName + "<br/>";
                }
            }
        }
        //st = Data.stations.Single(p => p.IDStation == station[arr[arr.Length-1]].id);
        //result += "Trạm kết thúc " + st.AddressNumber + ", " + st.StreetName + "\n";
        return result;
    }
    public static double toRealDistance(double x)
    {
        return x * 110000;
    }
    public static double toUnrealDistance(double x)
    {
        return x / 110000;
    }
    
}